//
// Created by isabella on 25-6-2.
//
#include "Sort.h"

vector<int> QuickSort::sort(vector<int> arr) {
    doSort(arr, 0, arr.size() - 1);
    return arr;
}

void QuickSort::doSort(vector<int>& nums, int low, int high) {
    if (low >= high) return;
    int mid = partition(nums, low, high);
    doSort(nums,low,mid-1);
    doSort(nums,mid+1,high);
}

int QuickSort::partition(vector<int>& nums, int low, int high) {
    auto swap=[&](int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    };

    int r=RandomUtils::get(low, high);
    swap(low, r);
    int pivot =nums[low];
    bool flag=false;
    while(low<high) {
        if(flag==false) {
            if(nums[high]<pivot) {
                nums[low]=nums[high];
                high++;
                flag=true;
            }
            high--;
        }else {
            if(nums[low]>=pivot) {
                nums[high]=nums[low];
                low--;
                flag=false;
            }
            low++;
        }
    }
    nums[low]=pivot;
    return low;
}